package listbyorder.access101_200.test105;

import listbyorder.utils.TreeNode;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/7 10:11
 */
public class Solution2 {

    // 相似的解法，指针略微的区别
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        return getAns(preorder, 0, len, inorder, 0, len);
    }

    private TreeNode getAns(int[] preorder, int pStart, int pEnd, int[] inorder, int iStart, int iEnd) {
        if (pStart == pEnd) return null;
        int root_val = preorder[pStart];
        TreeNode root = new TreeNode(root_val);
        int i_root_index = iStart;
        for (int i = iStart; i < iEnd; i++) {
            if (root_val == inorder[i]) {
                i_root_index = i;
                break;
            }
        }
        int leftNum = i_root_index - iStart;
        root.left = getAns(preorder, pStart + 1, pStart + leftNum + 1, inorder, iStart, i_root_index);
        root.right = getAns(preorder, pStart + leftNum + 1, pEnd, inorder, i_root_index + 1, iEnd);
        return root;
    }

}
